package com.eddie.tree.threadedbinarytree;

import lombok.Data;

/**
 * 创建HeroNode节点
 */
@Data
class HeroNode {
    private int no;
    private String name;
    private HeroNode left; //默认null
    private HeroNode right;//默认null

    /**
     * 如果leftType=0表示指向左子树，如果为1表示指向前驱节点
     */
    private int leftType;
    /**
     * 如果right=0表示指向右子树，如果为1表示指向后继节点
     */
    private int rightType;
    public static int count;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    /**
     * 编写前序遍历方法
     */
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右中序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    public HeroNode preOrderSearch(int id) {
        count++;

        //先输出父节点
        if (id == this.no) {
            return this;
        }
        //1.判断当前节点的左子节点是否为空，如果不为空，则递归向左查找
        //2.如果左递归谦虚查找，找到节点返回
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(id);
        }

        //说明在左子树找到了
        if (resNode != null) {
            return resNode;
        }
        //递归向右前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(id);
        }

        //直接返回结果，尽管没找到
        return resNode;
    }

    public HeroNode infixOrderSearch(int id) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(id);
        }
        if (resNode != null) {
            return resNode;
        } else if (this.no == id) {
            count++;
            return this;
        }

        if (this.right != null) {
            resNode = this.right.infixOrderSearch(id);
        }
        return resNode;
    }

    public HeroNode postOrderSearch(int id) {
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.postOrderSearch(id);
        }
        if (heroNode != null) {
            return heroNode;
        }
        if (this.right != null) {
            heroNode = this.right.postOrderSearch(id);
        }

        if (heroNode != null) {
            return heroNode;
        }
        count++;
        if (this.no == id) {
            return this;
        }
        return heroNode;
    }

    public void delHeroNode(int id) {
        //思路:
        /*
         1、因为二叉树是单向的，所以判断当前节点的子节点是否是要删除的，不能判断当前节点
         2、如果当前节点的左子节点不为空，并且就是要删除的节点，就将this.left =null;并且就返回（结束递归删除）
         3、如果当前节点的右子节点不为空，并且就是要删除的节点，就将this.right =null;并且就返回（结束递归删除）
         4、如果第二和第三部没有删除节点，那么需要向左子树进行递归
         5、如果第四部‍没有删除节点，那么需要向右 子树进行递归
         */
        if (this.left != null && this.left.no == id) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == id) {
            this.right = null;
            return;
        }
        //向左子树递归删除
        if (this.left != null) {
            this.left.delHeroNode(id);
        }

        //向左子树递归删除
        if (this.right != null) {
            this.right.delHeroNode(id);
        }
    }

    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

}